//1.库函数lower_bound和upper_bound
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0)
            return {-1, -1};
        
        int n = nums.size();
        vector<int> ret;
        auto ret_1 = std::lower_bound(nums.begin(), nums.end(), target);//起始位置
        auto ret_2 = std::upper_bound(nums.begin(), nums.end(), target);//终点后一个位置
        if(ret_1==nums.end() || *ret_1 != target)
             return {-1, -1};
        if(*(ret_2-1) != target)
             return {-1, -1};


        int ans1 = ret_1-nums.begin();
        int ans2 = ret_2-nums.begin()-1;
        

        return {ans1,ans2};

    }
};
//2.手动实现库函数--深入理解二分
class Solution {
public:
    int my_lower_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int ans = nums.size();
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                ans = mid;
                right = mid - 1; //不减一就死循环
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    int my_upper_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int ans = nums.size();
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                ans = mid;
                right = mid - 1;   //不减一就死循环
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return {-1, -1};

        int start = my_lower_bound(nums, target);
        int end = my_upper_bound(nums, target) - 1;   

        if (start < n && nums[start] == target) //如果返回n，n-1就是末尾，有效的，所以仅仅判断第一个
            return {start, end};
        return {-1, -1};
    }
};



